/*
 * @lc app=leetcode.cn id=63 lang=javascript
 *
 * [63] 不同路径 II
 */

// @lc code=start
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
  let steps = [];
  let m = obstacleGrid.length,
    n = obstacleGrid[0].length;
  for (let index = 0; index < m; index++) {
    steps[index] = new Array();
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      //判断当前格子是否有障碍，有障碍到不了
      if (obstacleGrid[i][j]) {
        //如果在入口有障碍无法到达任何地方
        if (i == 0 && j == 0) {
          return 0;
        }
        steps[i][j] = 0;
      } else {
        //边界情况 入口为一
        if (i == 0 && j == 0) {
          steps[i][j] = 1;
          //第一行只和前一位置有关
        } else if (i == 0 && j != 0) {
          steps[i][j] = steps[i][j - 1];
          //第一列之和上一位置有关
        } else if (j == 0 && i != 0) {
          steps[i][j] = steps[i - 1][j];
        } else {
          //状态转移方程
          steps[i][j] = steps[i - 1][j] + steps[i][j - 1];
        }
      }
    }
  }
  return steps[m - 1][n - 1];
};
// @lc code=end
